import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class MST1710 {
    /**
     * 面试题 17.10. 主要元素
     * 数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。
     * 示例 1：
     * 输入：[1,2,5,9,5,9,5,5,5]
     * 输出：5
     */
    public int majorityElement(int[] nums) {
            HashMap<Integer,Integer> hashMap=new HashMap<Integer, Integer>();
            int max=0;
            int value=0;
            if(nums.length<1){
                return -1;
            }
            for(int i=0;i<nums.length;i++){
                if (hashMap.containsKey(nums[i])){
                    hashMap.replace(nums[i],hashMap.get(nums[i])+1);
                }else {
                    hashMap.put(nums[i],1);
                }
            }

            for (int key : hashMap.keySet()) {
                if (hashMap.get(key)>max)
                {
                    max=hashMap.get(key);
                    value=key;
                }
            }
            if (max>nums.length/2){
                return  value;
            }else{
                return -1;
            }

        }

}
